// 解法1，递归，左节点--> 根节点 --> 右节点
function inOrderTraversal(root: TreeNode | null): any[] {
    if (!root) {
        return []
    }
    // 获取节点数据
    const res = []
    // 执行遍历：左节点--> 根节点 --> 右节点
    const inOrder =(node: TreeNode | null) =>{
        if(!node){
            return 
        }
        inOrder(node.left)
        res.push(node.val)
        inOrder(node.right)
    }
    inOrder(root)
    return res
}

// 解法2： 迭代法，迭代的时候需要显式地实现调用栈
// 本质上是在模拟递归，因为在递归的过程中使用了系统栈，所以在迭代的解法中常用Stack来模拟系统栈。
function inOrderTraversal1(root: TreeNode | null): any[] {
    if (!root) {
        return [];
    }
    // 获取节点数据
    const res:any = [];
    const stack: TreeNode[] = []
    while(root || stack.length){
        // 一直左遍历到头，把所有最左节点放入栈中
        if(root){
            stack.push(root);
            root = root.left;
        }else{
             // 从栈中拿出一个节点，获取该节点的值。然后遍历这个节点的右节点
            root = stack.pop();
            res.push(root.val);
            root = root.right;
        }
        // while(root){
        //     stack.push(root);
        //     root = root.left;
        // }
       
        // root = stack.pop();
        // res.push(root.val)
        // root = root.right
    }
    return res
}
// 解法三，MorrisMorris。空间复杂度是O（1）.
// 假设当前遍历到的节点为 root,
// 1如果 root有左节点，则找到 root左子树的最右节点（左子树的中序遍历时的最后一个节点， root节点在中序遍历时的前驱节点）, 记作predecessor.
// 如果predecessor.right === null， 则将predecessor.right设置为 root, 然后继续访问 root的left节点
// 如果predecessor.right !== null, ，测试说明我们已经遍历完成了 root的左子树，将precedessor.right设置为null，断开连接，将 root的值放入数组中； 然后开始访问 root的右孩子。
// 2如果 root 无左节点，则将 root的值加入答案数组中，然后遍历 root的右孩子
function inOrderTraversal13(root: TreeNode | null): any[] {
    if (!root) {
        return [];
    }
    // 获取节点数据
    const res = [];
    let predecessor = null;
    while(root){
        if(root.left){
            predecessor = root.left;
            // 一直遍历，找到最右边的节点，但是最后边节点要排除掉root
            while(predecessor.right && predecessor.right !== root){
                predecessor = predecessor.right;
            }
            // 如果predecessor.right === null， 则将predecessor.right设置为root, 然后继续访问x的left节点
            if(!predecessor.right){
                predecessor.right = root;
                root = root.left
            // 如果predecessor.right !== null, ，则说明我们已经遍历完成了 root的左子树，
            // 将 root的值放入数组中；将precedessor.right设置为null，断开连接， 然后开始访问 root的右孩子。
            }else{
                predecessor.right = null;
                res.push(root.val);
                root = root.right;
            }
            
        }else{
            res.push(root.val);
            root = root.right;
        }
    }
    return res
}